package main

import (
	"fmt"
	"math"
)

func RadixSort(arr []int) {
	max := 10
	for i := 0; i < max; i++ {
		count := [10]int{}
		output := make([]int, len(arr))
		for j := 0; j < len(arr); j++ {
			count[(arr[j]/(int(math.Pow10(i))))%10]++
		}
		for j := 1; j < 10; j++ {
			count[j] += count[j-1]
		}
		for j := len(arr) - 1; j >= 0; j-- {
			output[count[(arr[j]/(int(math.Pow10(i))))%10]-1] = arr[j]
			count[(arr[j]/(int(math.Pow10(i))))%10]--
		}
		arr = output
	}
	fmt.Println(arr)
}

func main() {
	arr := []int{329, 457, 657, 839, 436, 720, 355}
	RadixSort(arr)
}
